/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-09-04
 * Time: 20:11
 */
public class SearchArray2 {
    public boolean Find (int target, int[][] array) {
        // 暴力求解，不推荐
        // write code here
        // for (int i = 0 ; i < array.length ; i ++) {
        //     for (int j = 0 ; j < array[i].length ; j ++) {
        //         if (array[i][j] == target) {
        //             return true;
        //         }
        //     }
        // }
        // return false;

        //推荐方法：
        // 思路：从左下角开始走，走到边界如果没找到就不存在
        // 1.判断特殊情况
        if (array.length == 0) {
            return false;
        }
        if (array[0].length == 0) {
            return false;
        }
        int m = array.length;
        int n = array[0].length;
        int i = m-1;
        int j = 0;
        while (i >= 0 && j < n) {
            if (array[i][j] > target) {
                // target 大于该元素，向上走
                i --;
            } else if (array[i][j] < target) {
                // target 小于该元素，向右走
                j ++;
            } else {
                return true;
            }
        }
        return false;
    }
}
